#include "stdio.h"
#include <stdlib.h>
#define FALSE 0
#define TRUE 1
 struct Btree
{
    int data;
    struct Btree *lchild;
    struct Btree *rchild;
};

int search(struct Btree *T, int key, struct Btree *f, struct Btree **p)//搜索函数
{
    if(T ==NULL)
    {
        *p = f;
        return FALSE;
    }
    else if(T->data == key)
    {
        *p = T;
        return TRUE;
    }
    else if(T->data > key)
    {
        return search(T->lchild,key,T,p);
    }
    else 
    {
        return search(T->rchild,key,T,p);
    }
}

int insert_btree(struct Btree **T, int key)//插入元素
{
    struct Btree *p = NULL;
    struct Btree *s = NULL;
    if (!search(*T,key,NULL,&p))//查找不成功
    {
        s = (struct Btree *)malloc(sizeof(struct Btree));
        s->data = key;
        s->lchild = s->rchild = NULL;
        if(p == NULL)
        {
            *T = s;
            printf("1");
        }
        else if(key < p->data)
        {
            p->lchild = s;
            printf("2");
        }
        else 
        {
            p->rchild = s;
            printf("3");
        }
    return TRUE;
    }
    else return FALSE;
}

int main()
{
    int a[] = {3,2,1,4,5,7,9,0,13,65,84,35,97,56,20};
    struct Btree *T =NULL;
    struct Btree *p =NULL;
    struct Btree *f = NULL;
    for(int i = 0;i<15;i++)
    {
        insert_btree(&T,a[i]);
    }
    printf("%d\r\n",search(T,13, f, &p));
}